# Floyd-Warshall：如果图中的两个点 能通过权重更小的 中间点 到达，则更新路径

from tools.Conversion import Conversion
from tools.Input import Input
from tools.Output import Output


class FW:
    __name = 'Floyd Warshall'

    @staticmethod
    def do_floyd_warshall():
        g = Input.input_graph_matrix()  # 输入有向图
        # g = Conversion.graph_arr_2_matrix(Input.get_graph2(), direction=True)  # 获取一个图（例3.4.2）
        print('输入的图为：')
        Output.print_graph_matrix(g)

        v_set = g[0]  # 图的点集
        s_set = g[1]  # 图的边集
        precursor = FW.get_precursor(g)  # 图的前驱

        print('生成过程：')
        for k in range(len(v_set)):  # 遍历中间点
            print('遍历以', v_set[k], '为中间节点的路径：')
            for i in range(len(v_set)):  # 边集的每一行
                for j in range(len(v_set)):  # 边集的每一列
                    if s_set[i][j] > s_set[i][k] + s_set[k][j]:  # 如果i到j的权重大于通过中间点k到达
                        s_set[i][j] = s_set[i][k] + s_set[k][j]  # 更新i到j的最小权重
                        precursor[i][j] = v_set[k]  # 更新i到j的前驱节点
                        print('更新：', v_set[i], '到', v_set[j], '的最短路长', s_set[i][j], '前驱', precursor[i][j])
            print('更新最短路长：')
            Output.print_graph_matrix(g)
            print('更新前驱节点：')
            Output.print_graph_matrix([v_set, precursor])

        print('最短路长：')
        Output.print_graph_matrix(g)
        print('前驱节点：')
        Output.print_graph_matrix([v_set, precursor])

    ''' 创建并初始化图的前驱矩阵 '''

    @staticmethod
    def get_precursor(g):
        v_set = g[0]  # 图的点集
        s_set = g[1]  # 图的边集
        p = []
        for i in range(len(v_set)):
            p_line = []
            for j in range(len(v_set)):  # 不可达记无穷
                if s_set[i][j] == float('inf'):
                    p_line.append('inf')
                else:  # 可达，前驱节点记本身
                    p_line.append(v_set[i])
            p.append(p_line)
        return p
